package com.yx.study.leet.questionList.questionTwo;

import org.junit.Test;

/**
 * 53. 最大子数组和
 * https://leetcode.cn/problems/maximum-subarray/
 * */
public class Solution53 {
//    public int maxSubArray(int[] nums) {
//        int length = nums.length;
//        int[] dp = new int[length];
//        dp[0] = nums[0];
//        for (int i = 1; i < length; i++) {
//            if (dp[i - 1] > 0) {
//                dp[i] = dp[i - 1] + nums[i];
//            } else {
//                dp[i] = nums[i];
//            }
//        }
//        int res = dp[0];
//        for (int i = 1; i < length; i++) {
//            res = Math.max(res, dp[i]);
//        }
//        return res;
//    }

    public int maxSubArray(int[] nums) {
        int pre = 0;
        int res = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(res, pre);
        }
        return res;
    }


    @Test
    public void test(){
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        nums = new int[]{5,4,-1,7,8};
        nums = new int[]{-2,1,-3};
        System.out.println(maxSubArray(nums));
    }
}
